The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A graph G is said to be a cluster graph if G is a disjoint union of cliques (complete subgraphs), and a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs). In this work, we study the parameterized version of the NP-hard Bicluster Graph Editing problem, which consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an...
In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined...
Many parameterized problems (as the clique problem or the dominating set problem) ask, given an instance and a natural number k as parameter, whether there is a solution of size k. We analyze the relationship between the complexity of such a problem and the corresponding maximality (minimality) problem asking for a solution of size k maximal (minimal) with respect to set inclusion. As our results...
We show that every problem in MAX SNP has a lower bound on the optimum solution size that is unbounded and that the above guarantee question with respect to this lower bound is fixed parameter tractable. We next introduce the notion of “tight” upper and lower bounds for the optimum solution and show that the parameterized version of a variant of the above guarantee question with respect to the tight...
We prove that each parameterized counting problem in the class #[P] has a randomized fpt approximation algorithm using a W[P] oracle. Analoguous statements hold for #W[t] and #A[t] for each t≥1. These results are parameterized analogues of a theorem due to O.Goldreich and L.Stockmeyer.
An ordering of a graph G=(V,E) is a one-to-one mapping α: V →{1,2,..., |V|}. The profile of an ordering α of G is prfα(G)=∑v ∈ V(α(v)– min {α(u): u ∈N[v]}); here N[v] denotes the closed neighborhood of v. The profile prf(G) of G is the minimum of prfα(G) over all orderings α of G. It is well-known that prf(G) equals the minimum...
We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function fG of a graph G on n vertices. Our results are as follows: -) For graphs of bounded tree-width there is an OBDD of size O(logn) for fG that uses encodings of size O(logn) for the vertices; -) For graphs of bounded...
Matching and packing problems have formed an important class of NP-hard problems. There have been a number of recently developed techniques for parameterized algorithms for these problems, including greedy localization, color-coding plus dynamic programming, and randomized divide-and-conquer. In this paper, we provide further theoretical study on the structures of these problems, and develop improved...
The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter...
Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability. The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.
Up to now, most work in the area of parameterized complexity has focussed on exact algorithms for decision problems. The goal of this paper is to apply parameterized ideas to approximation. We begin exploration of parameterized approximation problems, where the problem in question is a parameterized decision problem, and the required approximation factor is treated as a second parameter for the problem.
A subset of vertices D ⊆ V of a graph G = (V,E) is a dominating clique if D is a dominating set and a clique of G. The existence problem ‘Given a graph G, is there a dominating clique in G?’ is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problem are NP-hard. We present an O(1.3390n) time algorithm that for an input graph on n vertices either computes...
We analyze edge dominating set from a parameterized perspective. More specifically, we prove that this problem is in for general (weighted) graphs. The corresponding algorithms rely on enumeration techniques. In particular, we show how the use of compact representations may speed up the decision algorithm.
We investigate the parameterized complexity of Maximum Independent Set and Dominating Set restricted to certain geometric graphs. We show that Dominating Set is W[1]-hard for the intersection graphs of unit squares, unit disks, and line segments. For Maximum Independent Set, we show that the problem is W[1]-complete for unit segments, but fixed-parameter tractable if the segments are axis-parallel.
We present a fixed parameter tractable algorithm for the Independent Set problem in 2-dir graphs and also its generalization to d -dir graphs. A graph belongs to the class of d -dir graphs if it is an intersection graph of segments in at most d directions in the plane. Moreover our algorithms are robust in the sense that they do not need the actual representation of the input graph and they answer...
Deciding whether two n-point sets A, B ∈ℝd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT. When |A|=m<|B|=n, the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that...
Resolving a noted open problem, we show that the Undirected Feedback Vertex Set problem, parameterized by the size of the solution set of vertices, is in the parameterized complexity class Poly(k), that is, polynomial-time pre-processing is sufficient to reduce an initial problem instance (G,k) to a decision-equivalent simplified instance (G′,k′) where k′ ≤k, and the number of vertices of G′ is bounded...
We provide first-time fixed-parameter tractability results for the NP-complete problems Maximum Full-Degree Spanning Tree and Minimum-Vertex Feedback Edge Set. These problems are dual to each other: In Maximum Full-Degree Spanning Tree, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For Minimum-Vertex Feedback Edge Set the task...
In the field of computational optimization, it is often the case that we are given an instance of an NP problem and asked to enumerate the first few ”best” solutions to the instance. Motivated by this, we propose in this paper a new framework to measure the effective enumerability of NP optimization problems. More specifically, given an instance of an NP problem, we consider the parameterized problem...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.